package com.zsp.test.Graph;

import java.util.*;

public class FriendRecommendation {

    // 图结构，存储每个用户及其好友列表
    private Map<Integer, Set<Integer>> graph = new HashMap<>();

    // 存储每个用户的PageRank值
    private Map<Integer, Double> pageRank = new HashMap<>();

    // 存储每个用户的个人资料
    private Map<Integer, UserProfile> userProfiles = new HashMap<>();

    // 阻尼系数，通常设置为0.85
    private double dampingFactor = 0.85;

    // 迭代次数
    private int iterations = 100;

    // 添加用户之间的边（好友关系）
    public void addEdge(int userOne, int userTwo) {
        // 如果userOne不存在于图中，则创建一个新的集合
        graph.computeIfAbsent(userOne, k -> new HashSet<>()).add(userTwo);
        // 确保userTwo也存在于图中，即使没有出边
        graph.putIfAbsent(userTwo, new HashSet<>());
    }

    // 添加用户的个人资料
    public void addUserProfile(int userId, UserProfile profile) {
        userProfiles.put(userId, profile);
    }

    // 计算每个用户的PageRank值
    public void calculatePageRank() {
        int totalNodes = graph.size();
        double initialPageRank = 1.0 / totalNodes; // 初始化PageRank值
        double threshold = 0.001; // 收敛阈值

        // 初始化每个节点的PageRank值
        for (Integer node : graph.keySet()) {
            pageRank.put(node, initialPageRank);
        }

        // 迭代更新PageRank值
        for (int iter = 0; iter < iterations; iter++) {
            Map<Integer, Double> newPageRank = new HashMap<>();
            boolean converged = true; // 标记是否收敛

            // 遍历每个节点，计算其新的PageRank值
            for (Integer node : graph.keySet()) {
                double inboundSum = 0.0;

                // 计算入边的PageRank贡献
                for (Integer otherNode : graph.keySet()) {
                    if (graph.get(otherNode).contains(node)) {
                        double otherNodePageRank = pageRank.get(otherNode);
                        int outboundLinks = graph.get(otherNode).size();
                        inboundSum += otherNodePageRank / outboundLinks;
                    }
                }

                // 根据PageRank公式计算新的PageRank值
                double newRank = (1 - dampingFactor) / totalNodes + dampingFactor * inboundSum;
                newPageRank.put(node, newRank);

                // 检查PageRank值是否收敛
                if (Math.abs(newRank - pageRank.get(node)) > threshold) {
                    converged = false;
                }
            }

            // 更新PageRank Map
            pageRank = newPageRank;

            // 如果收敛，提前终止迭代
            if (converged) {
                break;
            }
        }
    }

    // 推荐好友
    public List<Integer> recommendFriends(int userId) {
        // 获取已连接用户的集合
        Set<Integer> connectedUsers = new HashSet<>(graph.getOrDefault(userId, Collections.emptySet()));
        List<Integer> potentialFriends = new ArrayList<>();

        // 遍历所有用户，过滤出潜在好友
        for (Integer user : graph.keySet()) {
            // 排除已连接用户和自身
            if (!connectedUsers.contains(user) && user != userId) {
                // 计算相似度并检查是否超过阈值
                if (calculateSimilarity(userId, user) > 0.5) {
                    potentialFriends.add(user);
                }
            }
        }

        // 根据PageRank值排序
        potentialFriends.sort((a, b) -> Double.compare(pageRank.get(b), pageRank.get(a)));

        return potentialFriends;
    }

    // 计算两个用户之间的相似度
    private double calculateSimilarity(int userId1, int userId2) {
        UserProfile profile1 = userProfiles.get(userId1);
        UserProfile profile2 = userProfiles.get(userId2);

        // 地理位置相似度
        double locationSimilarity = profile1.getLocation().equals(profile2.getLocation()) ? 1.0 : 0.0;
        // 学校相似度
        double schoolSimilarity = profile1.getSchool().equals(profile2.getSchool()) ? 1.0 : 0.0;
        // 爱好相似度
        double hobbySimilarity = calculateJaccardSimilarity(profile1.getHobbies(), profile2.getHobbies());
        // 群组相似度
        double groupSimilarity = calculateJaccardSimilarity(profile1.getGroups(), profile2.getGroups());

        // 综合相似度
        return (locationSimilarity + schoolSimilarity + hobbySimilarity + groupSimilarity) / 4.0;
    }

    // 计算集合之间的Jaccard相似度
    private double calculateJaccardSimilarity(Set<String> set1, Set<String> set2) {
        Set<String> intersection = new HashSet<>(set1);
        intersection.retainAll(set2); // 计算交集

        Set<String> union = new HashSet<>(set1);
        union.addAll(set2); // 计算并集

        return (double) intersection.size() / union.size(); // 返回Jaccard相似度
    }

}

class UserProfile {
    private final String location; // 用户的地理位置
    private final String school; // 用户的学校
    private final Set<String> hobbies; // 用户的爱好
    private final Set<String> groups; // 用户所属的群组

    public UserProfile(String location, String school, Set<String> hobbies, Set<String> groups) {
        this.location = location;
        this.school = school;
        this.hobbies = hobbies;
        this.groups = groups;
    }

    public String getLocation() {
        return location;
    }

    public String getSchool() {
        return school;
    }

    public Set<String> getHobbies() {
        return hobbies;
    }

    public Set<String> getGroups() {
        return groups;
    }
}
